use std::{fmt::{self, Display, Formatter}};
use chrono::Local;

// 华容道游戏

// 游戏中的人物块数量
const BLOCK_COUNT: u8 = 10;
// 人物块加上空格块的数量
const BLOCK_AND_BLACK: usize = BLOCK_COUNT as usize + 2;
// 每个位置占用的bit数
const POSITION_BITS: u8 = 5;
// 获取一个位置的掩码
const POSITION_MASK: u64 = (1 << POSITION_BITS) - 1 ;
// 棋盘宽度
const BOARD_WIDTH: u8 = 4;
// 棋盘高度
const BOARD_HIGHT: u8 = 5;
// 棋盘上格子数
const CELL_COUNT: u8 = BOARD_HIGHT * BOARD_WIDTH;
// 字符串资源集长度
const RESOURCE_LENGTH: usize = 22;
// 字符串资源集
static STRING_RESOURCE: [&str; RESOURCE_LENGTH] = [
  "┏━━━━━━━━━━━━━━━━━━━━━━┓",  // 0
  "┃                      ┃",   // 1
  "┃          9           ┃",   // 2
  "┃         曹操         ┃",   // 3
  "┃        0 关羽        ┃",   // 4
  "┗━━━━━━━━━━━━━━━━━━━━━━┛",  // 5
  "┏━━━━━━━━━━┓",   // 6
  "┃          ┃",   // 7
  "┃     8    ┃",   // 8
  "┃   张飞   ┃",   // 9
  "┃     7    ┃",   // 10
  "┃   赵云   ┃",   // 11
  "┃     6    ┃",   // 12
  "┃   马超   ┃",   // 13
  "┃     5    ┃",   // 14
  "┃   黄忠   ┃",   // 15
  "┃   4 兵   ┃",   // 16
  "┃   3 兵   ┃",   // 17
  "┃   2 兵   ┃",   // 18
  "┃   1 兵   ┃",   // 19
  "┗━━━━━━━━━━┛",   // 20
  "            ",   // 21
];

const H_SIZE_INDEX: usize = 11;
// const V_SIZE_INDEX: usize = 12;
static BS: [[u8;13];BLOCK_AND_BLACK] = [
  [5,0,1,4,1,5,0,0,0,0,0, 2,1],
  [5,6,7,19,7,20,0,0,0,0,0, 1,1],
  [5,6,7,18,7,20,0,0,0,0,0, 1,1],
  [5,6,7,17,7,20,0,0,0,0,0, 1,1],
  [5,6,7,16,7,20,0,0,0,0,0, 1,1],
  [10,6,7,7,7,14,15,7,7,7,20, 1,2],
  [10,6,7,7,7,12,13,7,7,7,20, 1,2],
  [10,6,7,7,7,10,11,7,7,7,20, 1,2],
  [10,6,7,7,7,8,9,7,7,7,20, 1,2],
  [10,0,1,1,1,2,3,1,1,1,5, 2,2],
  [5,21,21,21,21,21,0,0,0,0,0, 1,1],
  [5,21,21,21,21,21,0,0,0,0,0, 1,1],
];

// 状态/局面
// 棋盘被划分成4*5的格子,从左到右,从上至下进行一维化编号
//  0,  1,  2,  3,
//  4,  5,  6,  7,
//  8,  9, 10, 11,
// 12, 13, 14, 15,
// 16, 17, 18, 19
// 用五个二进制位编码位置, 十个人物加两个空位视作12个棋子, 每个棋子一个位置, 共需要 60个二进制位
#[derive(Debug, Clone, Copy)]
pub struct State {
  curr: [u8; BLOCK_AND_BLACK],
  pub step_no: usize,
  lastmove: Move,
}

#[derive(Debug, Clone, Copy)]
struct Step {
  // 上一步在历史表中的索引
  pre: usize,
  // 当前步骤的状态
  state: u64,
  // 当前步数
  num: u16,
}

#[derive(Debug, Clone, Copy, PartialEq)]
struct  MoveItem {
  who: usize,
  origin: u8,
  finale: u8,
}

impl MoveItem {
  fn new(who: u8, origin: u8, finale: u8) -> Self {
    MoveItem { who: who as usize, origin, finale }
  }

  fn apply(self, state:&mut State) -> Result<(), String> {
    if self.origin < CELL_COUNT && self.finale < CELL_COUNT && self.who < BLOCK_AND_BLACK {
      if self.origin == state.curr[self.who] {
        state.curr[self.who] = self.finale;
        Ok(())
      } else {
        Err(format!("移动{}号块时, 预期原始位置为{}, 实际位置为{}", self.who, self.origin, state.curr[self.who]))
      }
    } else {
      Ok(())
    }
  }
}

// 一个移动
#[derive(Debug, Clone, Copy)]
pub struct Move {
  dir: u8,   // 移动方向, 0-上, 1-右, 2-下, 3-左
  picec: MoveItem,
  space_one: MoveItem,
  space_two: Option<MoveItem>,
}

impl Move {
  fn new(dir: u8, picec: MoveItem, space_one: MoveItem, space_two: Option<MoveItem>) -> Self {
    Move {picec, space_one, space_two, dir}
  }
}

struct Picec {
  id: usize
}

impl Picec {
  const WIDTH: [u8; BLOCK_AND_BLACK] = [2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1];
  const HIGHT: [u8; BLOCK_AND_BLACK] = [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 1, 1];
  // const NAME: [&'static str; BLOCK_COUNT] = ["关羽", "兵", "兵", "兵", "兵", "张飞", "赵云", "马超", "黄忠", "曹操"];
  pub fn width(&self) -> u8 {
    Self::WIDTH[self.id]
  }
  pub fn hight(&self) -> u8 {
    Self::HIGHT[self.id]
  }
  // pub fn name(&self) -> &'static str {
  //   Self::NAME[self.id]
  // }
}

// 状态实现
impl State {
  // 创建状态实例-初始状态
  pub fn new() -> Self {
    let mut state: u64 = 0;
    static DATA: [u8; BLOCK_AND_BLACK] = [9, 13, 14, 16, 19, 0, 3, 8, 11, 1, 17, 18];
    for i in DATA.iter().rev() {
      state = (state << POSITION_BITS) + (*i as u64);
    }
    let lastmove = Move::new(0_u8, MoveItem::new(0,0,0), MoveItem::new(0,0,0), None);
    State {lastmove, curr: DATA, step_no:0}
  }

  pub fn from(zip: u64) -> Self {
    let lastmove = Move::new(0_u8, MoveItem::new(0,0,0), MoveItem::new(0,0,0), None);
    State {lastmove, step_no: 0, curr: Self::u64_to_array(zip)}
  }

  pub fn from_array(curr: [u8; BLOCK_AND_BLACK]) -> State {
    let lastmove = Move::new(0_u8, MoveItem::new(0,0,0), MoveItem::new(0,0,0), None);
    State {lastmove, step_no: 0, curr}
  }

  pub fn next_state(self, m: Move) -> State {
    let mut s = self.clone();
    s.do_move(m);
    s
  }

  /// 只压缩
  fn array_to_u64(source_arr: [u8; BLOCK_AND_BLACK]) -> u64 {
    // 解压缩
    let arr = source_arr.map(|x|x as u64);
    // 压缩
    let mut zip = 0;
    for i in (0..BLOCK_AND_BLACK).rev() {
      zip = (zip << POSITION_BITS) + arr[i];
    }
    zip
  }

  fn u64_to_array(zip: u64) -> [u8; BLOCK_AND_BLACK] {
    let mut state = zip;
    let mut arr: [u8; BLOCK_AND_BLACK] = [0; BLOCK_AND_BLACK];
    for i in 0..BLOCK_AND_BLACK {
      arr[i] = (state & POSITION_MASK) as u8;
      state = state >> POSITION_BITS;
    }
    arr.map(|x|x.into())
  }

  /// 压缩
  pub fn zip(self) -> u64 {
    Self::array_to_u64(self.curr)
  }

  /// 局部排序并压缩
  pub fn reg_zip(self) -> u64 {
    Self::regular(self.curr)
  }

  /// 局部排序并压缩
  fn regular(soruce_arr: [u8; BLOCK_AND_BLACK]) -> u64 {
    // 解压缩
    let mut arr = soruce_arr.clone();
    // 局部排序, 小兵, 立将, 空格
    for (a, b) in [(1, 5), (5, 9), (10, 12)]{
      arr[a..b].sort();
    }
    State::array_to_u64(arr)
  }

  pub fn do_move(&mut self, themove: Move) -> bool {
    // println!("\n{themove}");
    if let Err(msg) = themove.picec.apply(self) {
      panic!("{msg}");
    }
    if let Err(msg) = themove.space_one.apply(self) {
      panic!("{msg}");
    }
    if let Some(m) = themove.space_two {
      if let Err(msg) = m.apply(self) {
        panic!("{msg}");
      }
    }
    self.step_no += 1;
    self.lastmove = themove;

    themove.picec.who == 9 && themove.picec.finale == 13
  }

  pub fn unzip_to_string(zip: u64) -> String{
    Self::u64_to_array(zip).map(|x| x.to_string()).join(",")
  }

  pub fn search(self) ->Vec<Move> {
    // 所谓探索, 即检查步骤对应的移动被执行后出现的局面是否已经出现过.
    // 若未出现过,则记录新的局面,并将新局面的所有被允许的移动放入待探索列表.

    // 即将探索(展开下一步)的步骤
    let mut curr = 0_usize;
    // 存放所有步骤(已探索和未探索), curr作为探索指针
    let mut history: Vec<Step> = Vec::<Step>::new();
    // 存放所有已探索的未重复局面
    let mut his_zip = Vec::<u64>::new();
    // 放入0号步骤(起始状态)
    history.push(Step{pre: 0, num: 0, state: self.zip()});
    // 起始状态对应的局面
    his_zip.push(self.reg_zip());

    let mut step_to_print = 20;
    // 存在未探索的步骤
    while curr < history.len() {
      // 从未探索的步骤索引得到待探索的局面
      let state = Self::from(history[curr].state);
      // 待探索局面对应的步骤数
      let num = history[curr].num + 1;
      // 待探索的局面中每一种被允许的移动
      for next in state.next_step() {
        let mut s = state.clone();
        if s.do_move(next) {
          // 找到答案, 把新局面放入队列, 用于构造答案对应的移动序列
          history.push(Step {pre: curr, num, state: s.zip()});
          println!("当前步数{step_to_print}, 发现局面{}个, 探索局面{curr}个, 找到答案, {}",
            history.len(), Local::now().format("%H:%M:%S"));
          // 返回找到的结果
          return Self::pick_result(history);
        } else {
          // 未找到结果, 则排序压缩, 判定是否新局面
          let zip = s.reg_zip();
          // println!("局面:[{}]", s.short_show());
          // print!("正则:[{}]", State::from(zip).short_show());

          if !his_zip.contains(&zip) {
            // 新局面
            his_zip.push(zip);
            history.push(Step {pre: curr, num, state: Self::array_to_u64(s.curr)});
          }
        }
      }
      curr += 1;

      if history[history.len() - 1].num > step_to_print {
        // for i in 0..history.len() {
        //   println!("第{i:^3}号,{}", history[i]);
        // }
        println!("当前步数{step_to_print}, 发现局面{}个, 探索局面{curr}个, 仍未找出结果, {}",
          history.len(), Local::now().format("%H:%M:%S"));
        step_to_print = step_to_print + 1;
      }
    }
    Vec::<Move>::new()
  }

  fn pick_any(history: &Vec<Step>, idx: usize) -> Vec<Move> {
    let mut n = idx;
    let mut his = Vec::<Step>::new();
    his.push(history[n]);
    while n > 0 {
      n = history[n].pre;
      his.push(history[n]);
    }
    his.reverse();
    let mut res = Vec::<Move>::new();
    for i in 1..his.len() {
      let state = Self::from(his[i - 1].state);
      // println!("第{}步:\n{state}", i-1);
      res.push(state.go_to(his[i].state));
    }
    res
  }

  fn pick_result(history: Vec<Step>) -> Vec<Move> {
    let n = history.len() - 1;
    Self::pick_any(&history, n)
  }

  fn go_to(self, zip: u64) -> Move {
    let arr = Self::u64_to_array(zip);
    let find = || {
      for i in 0..(BLOCK_COUNT as usize) {
        if self.curr[i] != arr[i] {
          return i
        }
      }
      panic!("没有发现两个状态有预期的差异!");
    };
    let who = find();
    let item = |who| MoveItem::new(who as u8, self.curr[who], arr[who]);
    Move::new(0, item(who), item(10), Some(item(11)))
  }

  // 当前局面接受的所有移动
  pub fn next_step(self) -> Vec<Move> {
    let mut result = Vec::<Move>::new();
    for who in 0..BLOCK_COUNT {
      for m in self.find_move(who) {
        // 不消耗第二个空格时, 检测是否能够连续移动
        if m.space_two == None {
          // 未消耗空格序号
          let sno = 21 - m.space_one.who as u8;
          // 未消耗空格所在坐标
          let pos = self.curr[sno as usize];
          // 提供棋子宽高
          let block = Picec {id: m.picec.who};

          // 同向, (可移动性(不区分单双格), (双格棋子的)新空格位置, 目标位置)
          let (ok, np, dist) = match m.dir {
            0 => (pos + BOARD_WIDTH == m.space_one.origin, if m.space_one.finale > BOARD_WIDTH {m.space_one.finale - BOARD_WIDTH} else {BLOCK_AND_BLACK as u8}, pos),
            1 => (m.space_one.origin + 1 == pos && pos % BOARD_WIDTH > 0, m.space_one.finale + 1, m.picec.finale + 1),
            2 => (m.space_one.origin + BOARD_WIDTH == pos,  m.space_one.finale + BOARD_WIDTH, m.picec.finale + BOARD_WIDTH),
            _ => (pos % BOARD_WIDTH < 2 && pos + 1 == m.space_one.origin, m.space_one.finale - 1, pos),
          };
          // 要移动的棋子
          if ok {
            let picec = self.moveto(who, dist);
            // 同向
            if block.width() * block.hight() == 2 {
              // 双格棋子
              let space_two = Some(self.moveto(sno, np));
              result.push(Move::new(m.dir, picec, m.space_one, space_two));
            } else {
              // 单格小兵
              let space_one = self.moveto(sno, picec.origin);
              result.push(Move::new(m.dir, picec, space_one, None));
            }
          } else if block.width() * block.hight() == 1 {
            let picec = self.moveto(who, pos);
            // 单格小兵, 需要考虑左右转弯
            if match m.dir {
              // 左转 或 右转
              0 => (pos % BOARD_WIDTH < 3 && pos + BOARD_WIDTH + 1 == m.picec.origin) || (pos % BOARD_WIDTH > 0 && pos + BOARD_WIDTH - 1 == m.picec.origin),
              1 => pos + BOARD_WIDTH - 1 == m.picec.origin || pos == m.picec.origin + BOARD_WIDTH + 1,
              2 => (pos % BOARD_WIDTH > 0 && pos == m.picec.origin + BOARD_WIDTH + 1) || (pos % BOARD_WIDTH < 3 && pos == m.picec.origin + BOARD_WIDTH - 1),
              _ => pos == m.picec.origin + BOARD_WIDTH - 1 || pos + BOARD_WIDTH + 1 == m.picec.origin,
            } {
              let space_one = self.moveto(sno, picec.origin);
              result.push(Move::new(m.dir, picec, space_one, None))
            }
          }
        }
        // 记录找到的可行移动
        result.push(m);
      }
    }
    result
  }

  pub fn find_move(&self, who: u8) -> Vec<Move> {
    // 棋子, 提供长宽属性
    let picec = Picec {id: who as usize};
    // 棋子当前坐标
    let pos = self.curr[who as usize];

    // 10号空格当前位置坐标
    let space_10 = self.curr[10];
    // 11号空格当前位置坐标
    let space_11 = self.curr[11];

    // println!("可移动性检测: 棋子: {who}, 位置{pos}, 两空格: ({space_10}, {space_11})");

    let mut res: Vec<Move> = Vec::<Move>::new();
    for dir in self.direction_iter() {
      // 当前方向是否顶到了边上
      if match dir {
        0 => pos < BOARD_WIDTH,
        1 => (pos + picec.width()) % BOARD_WIDTH == 0,
        2 => pos + picec.hight() * BOARD_WIDTH >= CELL_COUNT,
        _ => pos % BOARD_WIDTH == 0, 
      } {
        // 若已在边, 此方向铁定不能移动
        continue;
      }

      // 一次性计算出 (主目标空格位置坐标, 副目标空格位置坐标, 新(主)空格坐标, 新(副)空格坐标)
      let (dx1, dx2, ox1, ox2, dx) = match dir {
        0 => (
          pos - BOARD_WIDTH, 
          if picec.width() == 1 {CELL_COUNT} else {pos - BOARD_WIDTH + 1},
          pos + BOARD_WIDTH * (picec.hight() - 1),
          pos + BOARD_WIDTH * (picec.hight() - 1) + 1,
          pos - BOARD_WIDTH
        ),
        1 => (
          pos + picec.width(), 
          if picec.hight() == 1 {CELL_COUNT} else {pos + picec.width() + BOARD_WIDTH},
          pos, 
          pos + BOARD_WIDTH,
          pos + 1
        ),
        2 => (
          pos + picec.hight() * BOARD_WIDTH, 
          if picec.width() == 1 {CELL_COUNT} else {pos + picec.hight() * BOARD_WIDTH + 1},
          pos, 
          pos + 1,
          pos + BOARD_WIDTH,
        ),
        _ => (
          pos - 1, 
          if picec.hight() == 1 {CELL_COUNT} else {pos + BOARD_WIDTH - 1},
          pos + picec.width() - 1,
          pos + picec.width() - 1 + BOARD_WIDTH,
          pos - 1,
        ),
      };

      // println!("方向: {dir}, 目标位置: ({dx1}, {dx2}), 空格位置: ({ox1}, {ox2})");
      // 先检查所需的第一个位置
      if dx1 == space_10 || dx1 == space_11 {
        let picec = MoveItem::new(who, pos, dx);
        if dx2 == CELL_COUNT {
          // 只消耗一个空格的情况, 关键是被消耗空格的序号计算
          let sno: u8 = if dx1 == space_10 {10} else {11};
          let space_one = MoveItem::new(sno, self.curr[sno as usize], ox1);
          res.push(Move::new(dir, picec, space_one, None));
        } else if dx2 == space_10 {
          // 涉及双空格, 第一空格为10号空格
          let space_one = MoveItem::new(11, self.curr[11], ox1);
          let space_two = MoveItem::new(10, self.curr[10], ox2);
          res.push(Move::new(dir, picec, space_one, Some(space_two)));
        } else if dx2 == space_11 {
          // 涉及11号空格
          let space_one = MoveItem::new(10, self.curr[10], ox1);
          let space_two = MoveItem::new(11, self.curr[11], ox2);
          res.push(Move::new(dir, picec, space_one, Some(space_two)));
        }
      };
    };
    res
  }

  fn moveto(self, who: u8, new_pos: u8) -> MoveItem {
    MoveItem::new(who, self.curr[who as usize], new_pos)
  }

  fn direction_iter(&self) -> [u8;4] {
    [3,4,1,2].map(|x|{(x+self.lastmove.dir) % 4})
  }

  pub fn short_show(self) -> String {
    self.curr.map(|x|x.to_string()).join(",")
  }
}

impl Display for State {
  fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
    const SMALL_BLOCK_LINES: u8 = 5;
    // 用来输出的棋盘
    let mut board = [[RESOURCE_LENGTH;4];25];
    let state = self.curr;

    // 逐块处理
    for who in 0..BLOCK_AND_BLACK{
      // 每块对应的字符串资源
      let me = BS[who];
      // 此块在4*5的盘面上的横坐标
      let x = (state[who] % BOARD_WIDTH) as usize;
      // 此块在4*5的盘面上的纵坐标
      let y = state[who] / (BOARD_WIDTH);
      // println!("who:{who}, x:{x}, y:{y}, state[who]: {}", state[who]);
      // 表达块的字符串逐个
      for line in 1..=me[0] {
        let curr = (y * SMALL_BLOCK_LINES + line - 1) as usize;
        // 复制到用于输出的棋盘上
        board[curr][x] = me[line as usize] as usize;

        // (多次输出的时候才需要考虑)对于宽块
        if me[H_SIZE_INDEX] == 2 {
          // 右侧列需要清除(放一个不存在的资源索引)
          board[curr][x + 1] = RESOURCE_LENGTH;
        }
      }
    }
    
    // 输出盘面
    let mut res = Vec::<String>::new();
    for i in 0..25 {
      let mut line = Vec::<&str>::new();
      for j in 0..4 {
        if board[i][j] < RESOURCE_LENGTH {
          line.push(STRING_RESOURCE[board[i][j]]);
        }
      }
      res.push(line.join(""));
    }
    write!(f, "{}", res.join("\n"))
  }
}

impl Display for MoveItem {
  fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
    write!(f, "编号: {}, 原位置: {}, 新位置: {}", self.who, self.origin, self.finale)
  }
}

impl Display for Move {
  fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
    let s = if let Some(m) = self.space_two {format!("空格{}\n", m)} else {String::new()};
    write!(f, "棋子{}\n空格{}\n{}", self.picec, self.space_one, s)
  }
}

impl Display for Step {
  fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
    let s = State::from(self.state);
    write!(f, "步数:{:<2}前序号:{:<4}局:[{}] {}", self.num, self.pre, s.short_show(), s.reg_zip())
  }
}